#include <stdio.h>

struct
{
    int i, j;
    int pre;
}Qu[10];

void print(int front);

int mgpath(int xi, int yi, int xe, int ye);
    
int mg[10][10] = {
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
    {-1, 0, 0,-1, 0, 0, 0,-1, 0,-1},
    {-1, 0, 0,-1, 0, 0, 0,-1, 0,-1},
    {-1, 0, 0, 0, 0,-1,-1, 0, 0,-1},
    {-1, 0,-1,-1,-1, 0, 0, 0, 0,-1},
    {-1, 0, 0, 0,-1, 0, 0, 0, 0,-1},
    { 1, 0, 1, 0, 0, 0, 1, 0, 0,-1},
    {-1, 0,-1,-1,-1, 0,-1,-1, 0,-1},
    {-1,-1, 0, 0, 0, 0, 0, 0, 0,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
};

int main()
{
    int M = 8;
    int N = 8;

    mgpath(1, 1, M, N);

    return 0;
}
// entrance : xi,yi
// exit : xe, ye
int mgpath(int xi, int yi, int xe, int ye)
{
    int i, j, di;
    int front = -1, rear = -1;

    rear++;
    Qu[rear].i = xi;
    Qu[rear].j = yi;
    Qu[rear].pre = -1;
    mg[xi][yi] = -1; 
    while (front < rear)
    {
        front++;
        i = Qu[front].i;
        j = Qu[front].j;
        if (i == xe && j == ye)
        {
            print(front);
            return 1;
        }
        for (di = 0; di < 4; di++)
        {
            switch (di)
            {
            case 0: 
                i = Qu[front].i - 1;
                j = Qu[front].j;
                break;
            case 1: 
                i = Qu[front].i; 
                j = Qu[front].j + 1; 
                break;
            case 2: 
                i = Qu[front].i + 1;
                j = Qu[front].j;
                break;
            case 3:
                i = Qu[front].i;
                j = Qu[front].j - 1;
                break;
            default:
                break;

            }

            if (mg[i][j] == 0)
            {
                rear++;
                Qu[rear].i = i;
                Qu[rear].j = j;
                Qu[rear].pre = front;
                mg[i][j] = -1;
            }
        }
    }

    return(0);
}


void print(int front)
{
    int m = front, n, ns = 0;
    printf("\n");
    do
    {
        n = m;
        m = Qu[m].pre;
        Qu[n].pre = -1;
    } while (m != 0);

    printf("a safe path is : \n");
    while (m <= front)
    {
        if (Qu[m].pre == -1)
        {
            ns++;
            printf("\t(%d,%d)", Qu[m].i, Qu[m].j);
            if (ns % 5 == 0)
                printf("\n");
        }
        m++;
    }
    printf("\n");
}
